package org.example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test5 {
    //leetcode 47 全排列II https://leetcode.cn/problems/permutations-ii/
    public List<List<Integer>> ret;
    public List<Integer> path;
    public boolean[] vis;
    public List<List<Integer>> permuteUnique(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        vis = new boolean[21];
        Arrays.sort(nums);
        backtracking(nums);
        return ret;
    }

    public void backtracking(int[] nums) {
        if (path.size() == nums.length) {
            ret.add(new ArrayList<>(path));
        }
        for (int i = 0; i < nums.length; i++) {
            //因为数组中存在重复元素，所以不仅需要考虑同一层之间相同的数字产生的相同的排列情况
            //以及不同层之间相同数字产生的相同重复的排列情况 1 1 和 1 1

            //!vis[i]用来判断同一层之间的重复元素，也就是第i个位置选择的元素如果相等的话就会出现重复的结果
            //i==0的时候是数组的第一个元素，在这之前肯定不存在重复元素
            //nums[i-1] != nums[i]就说明当前元素和上面不同层之间的元素不存在重复值
            //vis[i-1]为true表示nums[i] == nums[i-1]，nums[i]可以选择，第i-1和第i个元素选择的值是可以重复的
            if (!vis[i] && (i == 0 || nums[i-1] != nums[i] || vis[i - 1])) {
                path.add(nums[i]);
                vis[i] = true;
                backtracking(nums);
                path.remove(path.size() - 1);
                vis[i] = false;
            }
        }
    }
}
